package JZ;

import jdk.nashorn.internal.runtime.FindProperty;

import java.util.*;

public class jz4 {
    public static void main(String[] args) {
        System.out.println(Find2(7, new int[][]{{1,2,8,9},{4,7,10,13},{6,8,11,15}}));

    }
    public static boolean Find1(int target, int [][] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                if(target == array[i][j])
                    return true;
            }
        }
        return  false;
    }

    public static boolean Find(int target, int [][] array) {
        int l = 0, r = array.length - 1;
        while (l < array[0].length && r > -1) {
            if(target == array[r][l]){
                return true;
            }
            else if(target > array[r][l]){
                l++;
            }
            else{
                r--;
            }
        }
        return  false;
    }

    public static boolean Find2(int target, int [][] array) {
        for (int i = 0; i < array.length; i++) {
            int l = 0, r = array[0].length;
            while(l < r){
                int mid = l + (l + r) / 2;
                if(array[i][mid] == target)
                    return true;
                else if(array[i][mid] > target)
                    r = mid;
                else
                    l = mid + 1;
            }
        }
        return  false;
    }
}
